/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils
{
	import flash.utils.Dictionary;
	
	//优先队列， Priority Queue
	public class PriorityQueue
	{
		//队列数据， data of the queue
		private var data:Array;
		
		//存储对象的优先权， the priority of the reference
		private var prior:Dictionary;
		
		//指向队尾， pointing to the tail of the queue
		private var rear:uint;
		
		public function PriorityQueue()
		{
			rear = 0;
			data = new Array();
			prior = new Dictionary();
		}
		
		//增加数据到队列中， add the given item into the queue
		public function enqueue(item:*, priority:uint):void
		{
			data[rear++] = item;
			prior[item] = priority;
		}
		
		//出队， get the first item in the queue and than remove it from the queue
		public function dequeue():*
		{
			//trace("rear is " + rear);
			var answer:*;
			if(rear == 0)
			{
				return null;
			}
			var t:uint = getPriority();
			answer = data[t];
			data.splice(t,1);
			rear--;
			delete prior[answer];
			return answer;
		} 
		
		//返回队首元素， get the first item
		public function peek():*
		{
			if(rear == 0)
			{
				return null;
			}
			return data[getPriority()];
		}
						
		//得到队列元素数量， get total number of the queue
		public function get size():uint
		{
			return data.length;
		}
		
		//队列是否为空， check if the queue is empty
		public function isEmpty():Boolean
		{
			return (rear == 0);
		}
		
		public function toString():String
		{
			return "[PriorityQueue, size=" + data.length + "]";
		}
		
		private function getPriority():uint
		{
			var flag:uint = prior[data[0]] as uint;
			var point:uint = 0;
			 
			for(var i:uint = 0; i < data.length; i++)
			{
				if(uint(prior[data[i]]) == 0)
				{
					point = i;
					break;
				} 
				if(flag > uint(prior[data[i]]))
				{
					flag = uint(prior[data[i]]);
					point = i;
				}
				
			}
			return point;
		}
	}
}